Anticipatory algorithms for online stochastic optimization have been shown to be very effective in a variety of areas, including logistics, reservation systems, and scheduling, as non-limiting examples. For such applications which typically feature purely exogenous uncertainty, the one-step anticipatory algorithm was shown theoretically to be close to optimal when the stochasticity of the problem, as measured by the anticipatory gap, was small.
Reference is herein made to the following publications:    [1] R. Bent and P. Van Hentenryck. Scenario-Based Planning for Partially Dynamic Vehicle Routing Problems with Stochastic Customers. Operations Research, 52(6), 2004.    [2] R. Bent and P. Van Hentenryck. “Waiting and Relocation Strategies in Online Stochastic Vehicle Routing.” IJCAI'07, 2007.    [3] J. Choi, M. Realff, and J. Lee. “Dynamic Programming in a Heuristically Confined State Space: A Stochastic Resource-Constrained Project Scheduling Application.” Computers and Chemical Engineering, 28(6-7):1039-1058, 2004.    [4] L. Mercier and P. Van Hentenryck. “Performance Analysis of Online Anticipatory Algorithms for Large Multistage Stochastic Programs.” IJCAI'07, 2007.    [5] L. Mercier and P. Van Hentenryck. “AMSAA: A Multistep Anticipatory Algorithm for Multistage Stochastic Combinatorial Optimization.” Submitted to CPAIOR, 2007.    [6] D. Parkes and A Duong. “An Ironing-Based Approach to Adaptive Online Mechanism Design in Single-Valued Domains.” In AAAI'07, pages 94-101, 2007.    [7] M. Thomas and H. Szczerbicka. “Evaluating Online Scheduling Techniques in Uncertain Environments.” In the 3rd Multidisciplinary International Scheduling Conference, 2007.    [8] P. Van Hentenryck and R. Bent. Online Stochastic Combinatorial Optimization. The MIT Press, Cambridge, Mass., 2006.
Online anticipatory algorithms [8] have been recently proposed to address a wide variety of online combinatorial optimization problems in areas such as logistics, networking, scheduling, and reservation systems. The applications emerged from progress in telecommunication and in information technologies which enable organizations to monitor their activities in real time and collect a significant amount of historical data. One-step anticipatory algorithms rely on two black-boxes: a conditional sampler to generate scenarios consistent with past observations and an offline solver which exploits the combinatorial structure of the application to solve the deterministic version of the problem. Their essence is to transform the multi-stage stochastic optimization application into a 2-stage problem by ignoring all non-anticipativity constraints but those of the current decision. This 2-stage problem is then approximated by sampling, and the approximated problem is solved optimally by computing the offline optimal solutions for all pairs (scenario, decision). One-step anticipatory algorithms were shown to be very effective on a variety of online stochastic combinatorial problems in dynamic fleet management [1, 2], reservation systems [8], resource allocation [6], and jobshop scheduling [7]. They were also analyzed theoretically in [4] in terms of the global anticipatory gap (GAG), which is a measure of the stochasticity of the application. The analysis shows that, when the GAG is small, anticipatory algorithms are guaranteed to return high-quality solutions when run with enough scenarios.